#include <stdio.h>
#include <string.h>

#include <iostream>
using std::cout;
using std::endl;

// 字符串(主串/单模式串)匹配

// 应用：grep -i 'hello' text.txt
/* 三、BM算法。高效，用于大文本搜索
 模式串从后往前匹配，一次移动多位所以高效
 1.坏字符：遇到不相等的字符，就从模式串从后往前找这个字符出现的位置（hash数组缓存每个字符的位置）
    1)找到则对齐坏字符
    abcdefg 坏字符c
    cbfd
    ->cbfd
    2)找不到则移动到坏字符后边
    abcgdefg 坏字符c
    defg
     ->defg
    缺点：字符集太大时耗内存
 2.好后缀：遇到相同的后缀，就从模式串从后往前找这个子串再出现的位置（hash数组缓存所有后缀组合位置+是否存在前后缀重叠）
    1)找到则对齐后缀
    aaacdeofg 好后缀cde
    cdexcd
     ->cdexcd
    2.1)找不到则判断模式串前后缀是否重叠，如果有重叠则移动到重叠处
    aaabcdexxcde 好后缀cde
    dexxcde 重叠de
       ->dexxcde
    2.2)没重叠则移动"模式串长度"位数
    aaabcdexxcda 好后缀cde
    fexxcde
         ->fexxcde
*/
void BoyerMoore() {}

int main() { return 0; }